from operator import mul

def gcd(a, b):
    """ Returns the greatest common denominator of a and b."""
    while True:
        if a == 0: return b
        if b == 0: return a

        if a > b: a = a % b
        else: b = b % a
        
    return a

def reduce_fraction(n, d):
    """ Reduces the fraction n/d. """
    g = gcd(n, d)
    return (n // g, d //g)

def factorial(n):
    """ Returns the factorial of n."""
    return reduce(mul, xrange(2, n + 1), 1)

def isqrt(n):
    """ Returns the integer square root of n."""
    xn = 1
    xn1 = (xn + n/xn)/2
    while abs(xn1 - xn) > 1:
        xn = xn1
        xn1 = (xn + n/xn)/2
    while xn1*xn1 > n:
        xn1 -= 1
    return xn1

def is_square(n):
    """ Checks whether n is a square number."""
    return n == isqrt(n)**2


